|
In algorithmic information theory (a subfield of computer science and mathematics), the Kolmogorov complexity (also known as descriptive complexity, Kolmogorov–Chaitin complexity, algorithmic entropy, or program-size complexity) of an object, such as a piece of text, is a measure of the computational resources needed to specify the object. It is named after Andrey Kolmogorov, who first published on the subject in 1963. For example, consider the following two strings of 32 lowercase letters and digits: abababababababababababababababab 4c1j5b2p0cv4w1x8rx2y39umgw5q85s7 The first string has a short English-language description, namely "ab 16 times", which consists of 11 characters. The second one has no obvious simple description (using the same character set) other than writing down the string itself, which has 32 characters. More formally, the complexity of a string is the length of the shortest possible description of the string in some fixed universal description language (the sensitivity of complexity relative to the choice of description language is discussed below). It can be shown that the Kolmogorov complexity of any string cannot be more than a few bytes larger than the length of the string itself. Strings, like the ''abab'' example above, whose Kolmogorov complexity is small relative to the string's size are not considered to be complex. The notion of Kolmogorov complexity can be used to state and prove impossibility results akin to Cantor's diagonal argument, Gödel's incompleteness theorem, and Turing's halting problem. ==Definition== The Kolmogorov complexity can be defined for any mathematical object, but for simplicity the scope of this article is restricted to strings. We must first specify a description language for strings. Such a description language can be based on any computer programming language, such as Lisp, Pascal, or Java virtual machine bytecode. If P is a program which outputs a string ''x'', then P is a description of ''x''. The length of the description is just the length of P as a character string, multiplied by the number of bits in a character (e.g. 7 for ASCII). We could, alternatively, choose an encoding for Turing machines, where an ''encoding'' is a function which associates to each Turing Machine M a bitstring Any string ''s'' has at least one description, namely the program: function GenerateFixedString() return ''s'' If a description of ''s'', ''d''(''s''), is of minimal length (i.e. it uses the fewest bits), it is called a minimal description of ''s''. Thus, the length of ''d''(''s'') (i.e. the number of bits in the description) is the Kolmogorov complexity of ''s'', written ''K''(''s''). Symbolically, :''K''(''s'') = |''d''(''s'')|. The length of the shortest description will depend on the choice of description language; but the effect of changing languages is bounded (a result called the ''invariance theorem''). 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Kolmogorov complexity」の詳細全文を読む スポンサード リンク
|